package com.wuxuan.algorithm_homework.random;

import java.util.Arrays;
import java.util.Random;

/**
 * 随机数
 *
 * 打乱数组
 * 给你一个整数数组 nums，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能的。
 * 实现 Solution class:
 * Solution(int[]nums)使用整数数组 nums 初始化对象
 * int[]reset() 重设数组到它的初始状态并返回
 * int[]shuffle() 返回数组随机打乱后的结果
 */
public class ShuffleArray {

    private int[] nums;
    private int[] shuffleNums;
    private Random random;

    public ShuffleArray(int[] nums) {
        this.nums = nums;
        shuffleNums = nums.clone();
        random = new Random();
    }

    /**
     * 重设数组到它的初始状态并返回
     * @return
     */
    public int[] reset() {
        return nums;
    }

    /**
     * 返回数组随机打乱后的结果
     * @return
     */
    public int[] shuffle() {
        //假设有[0, 1, 2]
        //一开始 i = 2
        for (int i = nums.length - 1; i >= 0; i--) {
            //[0, 1, 2, ..., i]
            int randomNum = random.nextInt(i + 1);
            swap(shuffleNums, i, randomNum);
        }

        return shuffleNums;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    public static void main(String[] args) {
        //示例 1:
        //输入
        //["Solution","shuffle","reset""shuffle"][[[1,2，3]],[],[]，[]]
        // 输出
        //[null,[3，1，2],[1，2，3]，[1，3，2]]
        int[] nums = {1, 2, 3};
        ShuffleArray test = new ShuffleArray(nums);

        System.out.println(Arrays.toString(test.shuffle()));
        System.out.println(Arrays.toString(test.reset()));
        System.out.println(Arrays.toString(test.shuffle()));

    }

}
